The present invention relates to systems and methods of storing and maintaining lists of key entries and the associated data entries thereof in a database, and, more particularly, to a system and method of improved database storage and maintenance using row index ordering.
The present invention discloses novel and efficient methods for storing and maintaining lists of Key entries and their Associated Data (AD) entries in flexible sequential schemes that allow fast Insert and Remove (update) algorithms involving shifts of entries in only a few rows, thereby significantly increasing the update rate and reducing the operating power consumption.
These storage and maintenance methods are significant improvements of the Insert and Remove algorithms presented in two previous inventions patented by HyWire Ltd., entitled “The Implementation of a Content Addressable Memory Using a RAM-Cell Structure” (U.S. patent application Ser. No. 10/229,054) and “RAM-Based Range Content Addressable Memory” (U.S. patent application Ser. No. 10/229,065). These two patents disclosed a method for implementing a Binary CAM and a Range CAM (RCAM), using a RAM structure surrounded by search logic in the RAM periphery, running a fast Search algorithm, and keeping lists of the keys and their associated data in perfect sequence by Insert and Remove algorithms.
The main concepts and principles of operation of the RAM-Based RCAM are very similar to those of the RAM-Based Binary CAM. The main difference is that, whereas the Binary CAM stores an ordered list of single integer keys and a corresponding list of their associated data, the RCAM stores a list of Key entries that represent range boundaries and a list of AD entries that correspond uniquely to these ranges. A key search in a Binary CAM results in an exact match, whereas a key search in an RCAM matches an entire range. The RCAM also stores a list of Associated Boundary Type entries which determine the validity of the corresponding ranges.
The basic concept underlying the approach of the RAM-Based Binary CAM and RCAM is storing and keeping the Key list and Associated Data list (with Associated Boundary Type list for RCAMs) in perfect sequence, as required by the fast search algorithm; these lists are typically arranged in Two-Dimensional Arrays (TDAs), which are readily implementable in conventional RAMs.
The update operation is preceded by a search procedure to determine the “update position”, which is the position where the submitted key is to be inserted or removed, provided that these operations are allowed. Key insertion is allowed only if the key is not included in the TDA, whereas key removal is possible only if it is already included in the TDA. The preliminary search procedure is identical for Binary CAMs and RCAMs, and is described in U.S. patent application Ser. No. 10/229,065. In a first step, the TDA row where the inserted/removed key may be located is identified, and subsequently, the precise key location within the TDA row is determined. The row identification is performed in the First Column Register (FC-Register), which stores the Key entries of the TDA first column in ascending sequence, corresponding to the contiguous monotonic order of the TDA Key entries.
The insertion and removal of entries in the TDAs, as presented in the above patents, are lengthy operations, because these entries are stored in contiguous monotonic order, with no empty TDA cells in between. The contiguity of entries in the TDA requires, in the case of ascending order (starting from the low end of the TDA), a forward/backward shift of the entries that are larger than the updated entry. Shifting a large number of entries contained in many rows (or columns) requires many read, shift and write steps, resulting in relatively long update time and significant power consumption.
There is therefore a recognized need for, and it would be highly advantageous to have, a system and method of storing and maintaining key entries in a database that is more efficient than those known heretofore, requires less repositioning of key entries during database updating, and enables updating operations to be performed as a background operation.